package leetcode.newcoder;

/**
 * Created by tiang on 2018/8/9.
 * 有n种钱币，每一种不限数量，求有多少种方法能够凑出目标钱数
 */
public class 钱币 {
    /**
     * 暴力破解
     * @param n 目标钱数
     * @param coins 钱币种类
     * @param i 只能采用从第i个小标之后的钱币，包括i
     * @return 种类数
     */
    private static long getMethods(int n, int[] coins, int i){
        if(n == 0)
            return 1;
        long result = 0;
        for(;i<coins.length;i++){
            if(n-coins[i]>=0) {
                result += getMethods(n - coins[i], coins, i);
            }
        }
        return result;
    }

    /**
     * 获取组合数量
     * @param n 目标钱数
     * @param coins 可用钱数
     * @param i 可用面额下标，从i开始到结束的钱币均可用
     * @return 组合数量
     */
    private static long getCombination(int n, int[] coins, int i, long[][] inner){
        if(i == coins.length-1)
            return 1;
        if(n == 0)
            return 1;
        if(n<0)
            return 0;
        if(inner[i][n]!=0)
            return inner[i][n];
        long result = getCombination(n-coins[i], coins, i, inner)+
                getCombination(n, coins, i+1, inner);
        inner[i][n] = result;
        return result;
    }
}
